/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/09
 */
package CodingTest.AC20190309;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 题目描述
 给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
 输入描述:
 无序整数数组A[n]
 输出描述:
 满足条件的最大乘积
 示例1
 输入

 3 4 1 2
 输出

 24

 思路：如果全为负数或全为正数，取最后三个数相乘既为最大乘积。关键是既有正数又有负数的情况（0其实可以看作负数）。
 如果有两个正数(例如[-2，-1，0，1，2])，
 那么最大值为arr[0] * arr[1] * arr[-1], 如果有一个正数(例如[-2，-1，0，2])，最大值同样为arr[0] * arr[1] * arr[-1]。
 */
//解法一：
public class MaxMutli {
    public long MaxMutli1(long[] a){
//        ArrayList<Integer> list= new ArrayList<Integer>();
//        for(int i = 0;i<a.length;i++){
//            list.add(a[i]);
//        }
        int len = a.length;
        Arrays.sort(a);
        return Math.max(a[len-1]*a[len-2]*a[len-3],a[len-1]*a[0]*a[1]);
    }
//解法二：
    public long MaxMutli2(long[] a) {
        long maxf = 0,maxs = 0,maxt = 0,minf = 0,mins = 0;
        for(int i = 0;i<a.length;i++){
            if(a[i] != 0){
                if(a[i]>=maxf){
                    maxt = maxs;
                    maxs = maxf;
                    maxf = a[i];
                }else if(a[i] >maxs){
                    maxt =maxs;
                    maxs = a[i];

                }else if(a[i]>maxt){
                    maxt = a[i];
                }else if(a[i]<minf){
                    mins = minf;
                    minf = a[i];

                }else if(a[i] <mins){
                    mins = a[i];
                }
            }else continue;
        }
        return Math.max(maxf*maxs*maxt,maxf*minf*mins);
    }

    public static void main(String[] args){
       List list = new ArrayList();
        Scanner sc =  new Scanner(System.in);
        int len = sc.nextInt();
        long[] a = new long[len];
        for(int j = 0;j<len;j++ ){
            a[j] = sc.nextLong();

        }

        MaxMutli m = new MaxMutli();
        System.out.println(m.MaxMutli2(a));

    }
}
